Vamos então entender mais sobre o conceito de tamanho de vizinhança.

Vejamos um exemplo para o problema do TSP com a vizinhança SWAP e 5 cidades:

Podemos fazer o SWAP do ponto um com todos os outros, gerando um total de 4 vizinhos. Da mesma forma, com o ponto 2, gerando mais 3 vizinhos. E com o 3 e 4, gerando mais 3 vizinhos.

Vamos definir agora o conjunto (possivelmente infinito) de todas as instâncias de um problema de tamanho \(n\) como \(\mathcal{F}(n)\). É possível então definir o tamanho de uma vizinhança como uma função \(f(n)\) do tamanho da instância:

Podemos então definir o tamanho da vizinhança do SWAP em função do número de pontos, como:

Agora, para determinar a ordem de crescimento de uma função \(f\), usamos a notação “Big-O”. De forma simplificada, essa notação reduz a função ao seu termo de crescimento mais acelerado. Por exemplo, no caso do SWAP, temos:

O termo de maior crescimento é \(\dfrac{n^2}{2}\), portanto dizemos que a ordem de crescimento de \(f(n)\) é:

Ainda, o tamanho da vizinhança SWAP cresce de forma quadrática em função do tamanho da instância \(n\).

A meta-heurística Large Neighborhood Search foi proposta por Shaw (1998 - Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems - Shaw)

1. DESTRUIÇÃO: Destrói parte da solução, usualmente de forma estocástica.
2. RECONSTRUÇÃO: Reconstrói a solução destruída, retornando-a para a factibilidade.

A vizinhança \(N(s)\) de uma solução é definida então pelas soluções que podem ser alcançadas pela aplicação do operador de destruição e depois de reconstrução.

Algumas considerações:

1. No método original, a função “aceita” só aceita soluções melhores, artigos posteriores usaram critérios como o SA.
2. É importante implementar uma taxa de destruição para o operador de destruição: se somente uma pequena parte da solução é destruída, a busca pode ficar muito limitada, se muito for destruída, é como um reinicio aleatório.
3. Shaw propõe um aumento gradativo da taxa de destruição, já Ropke and Pisinger selecionam de forma aleatória, para cada iteração, dentro de um range definido de acordo com o tamanho da instância.

Considere a seguinte notação:

1. \(\Omega^-\): Conjunto de todos os operadores de destruição.
2. \(\Omega^+\): Conjunto de todos os operadores de reconstrução.
3. \(\rho^-\): Conjunto com os pesos para cada operador de destruição.
4. \(\rho^+\): Conjunto com os pesos para cada operador de construção.

Agora precisamos entender como o mecanismo de escolha de operadores é auto regulado. Inicialmente os pesos \(\rho^+\) e \(\rho^-\) são iguais, de forma que todas as vizinhanças possuem as mesmas probabilidades de serem selecionadas. A escolha é feita pelo método da roleta, por exemplo, considere \(\rho^+\) para 5 vizinhanças:

As probabilidades de escolha ficam:

Para usar a roleta basta construirmos um vetor de probabilidades acumuladas:

E selecionarmos um número aleatório entre 0 e 1, determinando o operador da faixa selecionada

Os pesos \(\rho\) são ajustados dinamicamente baseado no desempenho armazenado de cada operador de destruição e reconstrução. Ao fim de cada iteração, um score \(\psi\) é calculado pela fórmula:

Em que \(\omega_1,\omega_2,\omega_3,\omega_4\) são parâmetros, geralmente com \(\omega_1 \geq \omega_2 \geq \omega_3 \geq\omega_4\). Ou seja, um alto valor de \(\mathbb{\psi}\) indica que a iteração (portanto operador de destruição e reconstrução) foi um sucesso.

Agora, com o valor de \(\psi\) os pesos \(\rho^+\) e \(\rho^-\) podem ser atualizados. Considerando \(a\) e \(b\) os índices dos operadores de destruição e reconstrução usados na última iteração, temos que:

Com \(\alpha \in [0,1]\). O parâmetro \(\alpha\) é chamado de decaimento (decay), e controla o quão sensível os pesos são às mudanças na performance dos operdores. Altos valores de \(\alpha\) são mais conservadores, mantendo a maior parte dos novos pesos como estavam antes da iteração. Já valores baixos favorecem mais alterações.

Vejamos um exemplo. Suponha que estamos na primeira iteração, portanto :

Considerando ainda que neste iteração usamos a vizinhança de destruição 0 (\({\color{#b6321d}a = 0}\)) e de reconstrução 2 (\({\color{#b6321d}b = 2}\).)

Com os seguintes valores de \(\omega\)

Com os seguintes valores de \(\omega\)

E finalmente, após essa iteração a nova solução ficou melhor que a atual.

Assim, precisamos usar as fórmulas:

Com \(\psi = 4\), \(a = 0\) e \(b = 2\). Só faltando determinar o coeficiente de sensibilidade \(\alpha\). Vamos calcular com 2 valores de \(\alpha\) e ver o que ocorre (0.2 e 0.8):

Dessa forma, os novos vetores de pesos (para os dois valores de \(\alpha\)) ficam:

O que confirma que o \(\alpha\) determina a sensibilidade dos pesos a mudanças - um \(\alpha\) menor gera pesos mais sensíveis, e um \(\alpha\) maior gera menos sensibilidade.

1. As meta-heurísticas LNS e ALNS são usadas quando as vizinhanças para um problema são muito grandes, de forma que os algoritmos trabalham com vizinhanças implícitas, por meio dos operadores de destruição e reconstrução.
2. Também podem ser usadas em problemas que a definição de vizinhanças não é tão clara, ou mesmo não é possível.
3. Se a solução inicial foi criada por um algoritmo guloso, podemos aproveitar a própria heurística de escolha dos elementos gulosos como um operador de reconstrução. Assim, somente determinando um operador de destruição já temos uma meta-heurística muito poderosa de forma simples a partir do greedy.
4. Devido a alta flexibilidade da escolha de operadores no ALNS, esta meta-heurística se encaixa muito bem para ser usada em mathheuristics (por exemplo, destruindo uma parte da solução e reconstruindo-a usando um modelo matemático com métodos exatos)